package com.shr.code_interview;

public class Solution_53 {
    public int GetNumberOfK(int [] array , int k) {
        int low = 0;
        int up = array.length - 1;
        int first = -1, last = -1 ;
        while(low <= up){
        	int mid = (low + up) / 2;
        	if(array[mid] < k)
        		low = low+1;
        	else if(array[mid] > k)
        		up = up - 1;
        	else{
        		if(mid==0 || array[mid - 1] != k){
        			first = mid;
        			break ;
        		}else up = mid - 1;
        	}
        }
        
        low = 0;
        up = array.length - 1;
        while(low <= up){
        	int mid = (low + up) / 2;
        	if(array[mid] < k)
        		low = low+1;
        	else if(array[mid] > k)
        		up = up - 1;
        	else{
        		if(mid == array.length-1 || array[mid + 1] != k){
        			last = mid;
        			break ;
        		}else low = mid + 1;
        	}
        }
        
        if(first==-1 && last==-1)
        	return 0;
        else return last-first+1;
    }
}
